W8. Последовательности, ряды, линейные рекуррентные соотношения

Quiz | Flashcards

1. Краткое содержание

1.1 Введение: последовательности (sequences)

Sequence — упорядоченный список чисел; формально это функция с подмножества \(\mathbb N\) (например \(\{0,1,2,\dots\}\) или \(\{1,2,3,\dots\}\)) в множество значений. Элементы называют terms (членами); пишут \(\{a_n\}\), где \(a_n\) — член с индексом \(n\).

1.1.1 Арифметическая прогрессия (arithmetic progression)

Постоянная разность соседних членов — common difference \(d\):

• Формула: \(a_n = a_0 + nd\)
• Пример: \(-10,-5,0,5,10,\dots\) при \(a_0=-10\), \(d=5\).

1.1.2 Геометрическая прогрессия (geometric progression)

Каждый следующий член получается умножением на фиксированное \(t\neq 0\) — common ratio:

• Формула: \(a_n = a_0 \cdot t^n\)
• Пример: \(1,-2,4,-8,16,\dots\) при \(a_0=1\), \(t=-2\).

1.2 Рекурсивно заданные последовательности

Recursion / recurrence — определение члена через предыдущие; нужны initial conditions.

• Рекурсия — когда определение ссылается на «более простую» копию той же структуры.
• Пример: числа Фибоначчи: \(f_0=0\), \(f_1=1\), \(f_{n+2}=f_{n+1}+f_n\); \(0,1,1,2,3,5,8,\dots\).

1.3 Ряды (series)

Series — сумма членов последовательности.

1.3.1 Суммирование (\(\sum\))

\(S(n)=\sum_{i=m}^{n} a_i\); \(i\) — index of summation, \(m\) — lower limit, \(n\) — upper limit. Рекурсивно: \(S(m)=a_m\), \(S(n+1)=S(n)+a_{n+1}\).

1.3.2 Произведение (\(\prod\))

\(P(n)=\prod_{i=m}^{n} a_i\). Факториал: \(n!=\prod_{i=1}^{n} i\), при этом \(0!=1\), \((n+1)!=(n+1)n!\).

1.3.3 Арифметический ряд

\[\sum_{i=0}^{n} (a_0 + id) = (n+1)a_0 + d \frac{n(n+1)}{2}\]

1.3.4 Геометрический ряд

При \(t\neq 1\): \[\sum_{i=0}^{n} a_0 t^i = a_0 \frac{t^{n+1}-1}{t-1}\]

1.4 Линейные рекуррентные последовательности (linear recurrence)

Linear recurrence порядка \(k\):

\[a_{n+k} = t_1 a_{n+k-1} + t_2 a_{n+k-2} + \dots + t_k a_n\]

1.4.1 Решение линейных рекуррентностей 2-го порядка

Цель — closed form для \(a_n\). Для \(a_{n+2} - t_1 a_{n+1} - t_2 a_n = 0\):

1. Characteristic equation: \(\chi(\lambda)=\lambda^2-t_1\lambda-t_2=0\).
2. Корни \(p_1,p_2\).
3. Различные корни: \(a_n=c_1 p_1^n+c_2 p_2^n\).
4. Кратный корень \(p\): \(a_n=(c_1 n+c_2)p^n\).
5. Константы \(c_1,c_2\) из начальных условий.

Пример (различные корни): \(a_{n+2}=3a_{n+1}-2a_n\), \(a_0=1,a_1=3\) → \(\lambda^2-3\lambda+2=0\), \(p=1,2\), \(a_n=2^{n+1}-1\).

Пример (кратный корень): \(a_{n+2}=4a_{n+1}-4a_n\), \(a_0=2,a_1=1\) → \((\lambda-2)^2\), \(a_n=(2-\tfrac32 n)2^n\).

1.4.2 Фибоначчи и формула Бине

\(\lambda^2-\lambda-1=0\), \(\phi=\frac{1+\sqrt5}{2}\), второй корень \(\frac{1-\sqrt5}{2}\):

\[f_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right)\]

1.5 Системы рекуррентностей

Систему часто сводят к одному уравнению большего порядка: из \(a_{n+1}=a_n+b_n\), \(b_{n+1}=a_n-b_n\) выражают \(b_n=a_{n+1}-a_n\), подставляют и получают, например, \(a_{n+2}=2a_n\) (см. примеры).

---

2. Определения

• Sequence — упорядоченный список (функция с \(\mathbb N\)).
• Arithmetic progression — постоянная разность соседних членов.
• Geometric progression — постоянное отношение соседних членов.
• Recursion — определение через само себя на более простом уровне.
• Series — сумма членов последовательности.
• Arithmetic series — сумма членов арифметической прогрессии.
• Geometric series — сумма членов геометрической прогрессии.
• Linear recurrence sequence — линейная комбинация фиксированного числа предыдущих членов.
• Characteristic equation — алгебраическое уравнение, связанное с линейной рекуррентностью.

---

3. Формулы

• Arithmetic progression: \(a_n = a_0 + nd\)
• Geometric progression: \(a_n = a_0 \cdot t^n\)
• 2-й порядок, различные корни \(p_1,p_2\): \(a_n = c_1 p_1^n + c_2 p_2^n\)
• 2-й порядок, кратный корень \(p\): \(a_n = (c_1 n + c_2) p^n\)

---

4. Примеры

4.1. Решить рекуррентности (Лаба 7, Задание 1)

1. \(a_0 = 15, a_{n+1} = a_n - 4\)
   
2. \(a_0 = -1, a_{n+1} = (-2)a_n\)
   
3. \(a_0 = 1, a_1 = 3, a_{n+2} = 3a_{n+1} - 2a_n\)
   
4. \(a_0 = 2, a_1 = 1, a_{n+2} = 4a_{n+1} - 4a_n\)

Показать решение

(a) Арифметическая: \(a_n=15-4n\).

(b) Геометрическая: \(a_n=-(-2)^n\).

(c) \(\lambda^2-3\lambda+2=0\), корни \(1,2\) → \(a_n=2^{n+1}-1\).

(d) \((\lambda-2)^2\), \(a_n=(2-\frac32 n)2^n\).

4.2. Системы рекуррентностей (Лаба 7, Задание 2)

Переписать и решить (общее решение \(a_n\)):

1. \(\begin{cases} a_{n+1} = 2a_n + b_n \\ b_{n+1} = a_n - b_n \end{cases}\)
   
2. \(\begin{cases} a_{n+1} = a_n + 2b_n \\ b_{n+1} = 3a_n - 2b_n \end{cases}\)

Показать решение

(a) \(b_n=a_{n+1}-2a_n\), подстановка даёт \(a_{n+2}=a_{n+1}+3a_n\), характеристическое \(\lambda^2-\lambda-3=0\), \(a_n=c_1\big(\frac{1+\sqrt{13}}2\big)^n+c_2\big(\frac{1-\sqrt{13}}2\big)^n\).

(b) \(b_n=\frac{a_{n+1}-a_n}{2}\), после подстановок \(a_{n+2}+a_{n+1}-8a_n=0\), корни \(\frac{-1\pm\sqrt{33}}2\), \(a_n=c_1(\frac{-1+\sqrt{33}}2)^n+c_2(\frac{-1-\sqrt{33}}2)^n\).

4.3. Строки над \(\{0,1,2\}\) без 00 и 11 (Лаба 7, Задание 3)

Сколько строк длины \(n\) без двух подряд идущих нулей и без двух подряд единиц?

Показать решение

Через окончания на 0/1/2 получают \(a_n=2a_{n-1}+a_{n-2}\) с \(a_0=1\) (пустая строка), \(a_1=3\).

Ответ: \(a_n = 2a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=3\).

4.4. Пароли: буква/спецсимвол только перед цифрой (Лаба 7, Задание 4)

Цифры 0–9, 52 буквы, 8 спецсимволов + - _ & % * ( ); после буквы или спецсимвола обязательно цифра. Сколько допустимых паролей длины 8?

Показать решение

Пусть \(D_n\) — оканчивается цифрой, \(L_n\) — буквой/спецсимволом; \(a_n=D_n+L_n\), \(D_n=10a_{n-1}\), \(L_n=60D_{n-1}\) → \(a_n=10a_{n-1}+600a_{n-2}\), \(a_1=70\), \(a_2=1300\).

Ответ: \(a_n=10a_{n-1}+600a_{n-2}\), \(a_1=70\), \(a_2=1300\) (значение \(a_8\) удобно считать по рекуррентности).

4.5. Разбиение отрезка длины \(n\) на куски 1,2,3 (Лаба 7, Задание 5)

Без трёх подряд кусков длины 1.

Показать решение

Добавление «1» запрещено, если предыдущая конфигурация длины \(n-1\) уже оканчивается на «11»; число таких — \(a_{n-3}\). Итого \(a_n=(a_{n-1}-a_{n-3})+a_{n-2}+a_{n-3}=a_{n-1}+a_{n-2}\). Начальные: \(a_1=1\), \(a_2=2\), \(a_3=3\).

Ответ: \(a_n=a_{n-1}+a_{n-2}\), \(a_1=1\), \(a_2=2\).

4.6. Битовые строки без двух единиц подряд (Лаба 7, Задание 6)

Сколько двоичных строк длины \(n\) без «11»?

Показать решение

Стандартно \(F(n)=F(n-1)+F(n-2)\), \(F(1)=2\), \(F(2)=3\) (сдвиг относительно классического Фибоначчи).

Ответ: \(F(n)=F(n-1)+F(n-2)\), \(F(1)=2\), \(F(2)=3\).

4.7. Система к одному уравнению (Лаба 7, Задание 7)

\[ \begin{cases} a_{n+1} = a_n + b_n \\ b_{n+1} = a_n - b_n \end{cases} \] Вывести рекуррентность 2-го порядка для \(a_n\).

Показать решение

\(b_n=a_{n+1}-a_n\), подстановка даёт \(a_{n+2}=2a_n\).

Ответ: \(a_{n+2}=2a_n\).

4.8. Сумма \(S(n)=\sum_{i=1}^{n} i\) (Туториал 7, Задание 1)

Записать рекурсивно.

Показать решение

\(S(1)=1\), \(S(n+1)=S(n)+(n+1)\).

Ответ: \(S(1)=1\), \(S(n+1)=S(n)+n+1\).

4.9. \(\sum_{i=15}^{n+3} i\) через \(S\) (Туториал 7, Задание 2)

\(S(n)=\sum_{i=1}^{n} i\).

Показать решение

\(\sum_{i=15}^{n+3} i = S(n+3)-S(14)\).

Ответ: \(S(n+3)-S(14)\).

4.10. Факториал рекурсивно (Туториал 7, Задание 3)

Показать решение

\(1!=1\), \((n+1)!=(n+1)n!\) (часто также \(0!=1\)).

Ответ: \(1!=1\), \((n+1)!=(n+1)n!\).

4.11. \(\prod_{i=4000}^{n+2} i\) через факториалы (Туториал 7, Задание 4)

Показать решение

\(\dfrac{(n+2)!}{3999!}\).

Ответ: \(\dfrac{(n+2)!}{3999!}\).

4.12. \(a_1=-1\), \(a_{n+1}=-a_n\) (Туториал 7, Задание 5)

Показать решение

Характеристическое \(\lambda+1=0\) → \(a_n=(-1)^n\) (согласовано с \(a_1=-1\) при индексации с 1: \(a_n=(-1)^n\)).

Ответ: \(a_n=(-1)^n\).

4.13. \(a_0=3\), \(a_{n+1}=2a_n\) (Туториал 7, Задание 6)

Показать решение

\(a_n=3\cdot 2^n\).

Ответ: \(a_n=3\cdot 2^n\).

4.14. \(a_0=2,a_1=-1\), \(a_{n+2}=a_n\) (Туториал 7, Задание 7)

Показать решение

\(\lambda^2-1=0\), \(a_n=\frac12+\frac32(-1)^n=\dfrac{1+3(-1)^n}{2}\).

Ответ: \(a_n=\dfrac{1+3(-1)^n}{2}\).

4.15. \(a_0=1,a_1=0\), \(a_{n+2}=2a_{n+1}-a_n\) (Туториал 7, Задание 8)

Показать решение

Кратный корень \(1\): \(a_n=1-n\).

Ответ: \(a_n=1-n\).

4.16. Двоичные строки без 00 и 11 (Туториал 7, Задание 9)

Над алфавитом \(\{0,1\}\).

Показать решение

Допустимые строки чередуются: для \(n\ge1\) всего две (\(010\dots\) и \(101\dots\)). Ответ: \(a_1=2\), далее \(a_n=2\) при всех \(n\ge1\).

4.17. Система рекуррентностей → одно уравнение 2-го порядка (Туториал 7, Задание 10)

Переписать как одно рекуррентное соотношение второго порядка для \(a_n\): \[ \begin{cases} a_{n+1} = a_n + b_n \\ b_{n+1} = a_n - b_n \end{cases} \]

Показать решение

1. Из первого уравнения: \(b_n = a_{n+1} - a_n\).
2. Сдвиг индекса в первом: \(a_{n+2} = a_{n+1} + b_{n+1}\).
3. Подставить \(b_{n+1} = a_n - b_n\): \(a_{n+2} = a_{n+1} + a_n - b_n\).
4. Заменить \(b_n = a_{n+1} - a_n\): \(a_{n+2} = a_{n+1} + a_n - (a_{n+1} - a_n) = 2a_n\).

Ответ: \(a_{n+2} = 2a_n\).